package 题目集.单调栈or队列.单调栈.保留可能性;

import org.junit.Test;

/**
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 * https://leetcode.cn/problems/remove-duplicate-letters/description/
 */
public class 去除重复字母 {
    /**
     * 要去掉的字符：
     *      我们要保留的是一个升序的序列，遍历到当前字符时，先判断当前字符是否比之前的大，如果不能保证升序，则判断之前的字符是否在后面出现过，如果出现过，则删除之前的字符
     *      如果当前字符在栈中出现过，则不添加（因为栈中元素已经是升序的）
     */
    public String removeDuplicateLetters(String s) {
        char[] chars = s.toCharArray();
        int[] count = new int[26];  //每个字符出现的次数
        boolean[] visited = new boolean[26];    //是否在栈中出现过
        int[] stack = new int[chars.length];
        int top = -1;
        for (char c : chars) {
            count[c - 'a']++;
        }
        for (int i = 0; i < chars.length; i++) {
            count[chars[i] - 'a']--;
            if (!visited[chars[i] - 'a']) {
                //删除之前比当前字符串大，且会重复的字符。
                while (top != -1 && chars[i] < chars[stack[top]] && count[chars[stack[top]] - 'a'] > 0) {
                    visited[chars[stack[top]] - 'a'] = false;
                    top--;
                }
                stack[++top] = i;
                visited[chars[i] - 'a'] = true;
            }
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i <= top; i++) {
            builder.append(chars[stack[i]]);
        }
        return builder.toString();
    }

    @Test
    public void test() {
        System.out.println(removeDuplicateLetters("edebbed"));
        System.out.println(removeDuplicateLetters("abacb"));
        System.out.println(removeDuplicateLetters("cbacdcbc"));
    }
}
